/*
题目: 会议室Ⅲ
给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

    每场会议都会在未占用且编号 最小 的会议室举办。
    如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
    当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。
https://leetcode.cn/problems/meeting-rooms-iii
 */
public class MostBooked {
    public class Pair {
        long endTime ;// 结束时间
        int room ; // 房间号
        public Pair(long meeting, int room) {
            this.endTime = meeting;
            this.room = room;
        }
    }

    public int mostBooked(int n, int[][] meetings) {
        PriorityQueue<Integer> freeRoom = new PriorityQueue<> ();
        for (int i = 0; i < n; i++) freeRoom.offer(i);

        Arrays.sort(meetings, (int[] o1, int[] o2) -> {return o1[0] - o2[0];});
        // 按照结束时间排序, 存的是会议信息
        PriorityQueue<Pair> busyRoom = new PriorityQueue<> ((Pair o1, Pair o2) -> {
            int diff = (int) (o1.endTime - o2.endTime);
            if (diff != 0) {
                return diff;
            } else {
                return o1.room - o2.room;
            }
        });

        int[] count = new int[n]; // 记录房间出现的次数
        for (int i = 0; i < meetings.length; i++) {
            while (!busyRoom.isEmpty() && meetings[i][0] >= busyRoom.peek().endTime) {// 开始时间 大于 最早结束的会议
                freeRoom.offer(busyRoom.poll().room);
            }
            if (!freeRoom.isEmpty()) {
                int room = freeRoom.poll(); // 房间号
                busyRoom.offer(new Pair(meetings[i][1], room)); // 分配会议号和房间号
                count[room]++;
            } else { // 没有空的
                if (busyRoom.peek().endTime > meetings[i][0]) { // 开始时间 小于 最早结束的会议
                    Pair top = busyRoom.poll();
                    count[top.room] ++; // 使用次数
                    long tmp = top.endTime + (long) (meetings[i][1] - meetings[i][0]);
                    busyRoom.offer(new Pair(tmp, top.room));
                }
            }
        }

        int src = 0;
        for (int i = 1; i < count.length; i++) {
            if (count[src] < count[i]) {
                src = i;
            }
        }
        return src;
    }
}
